package com.interview.write.DemoFive1;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class TreeNode {

    int key;

    TreeNode left;

    TreeNode right;


    public TreeNode(int key) {
        left = null;
        right = null;
        this.key = key;
    }


    //建立一颗二叉树
    public List<TreeNode> createTree(){

        int[] array = {1,2,3,4,5,6,7,8,9};

        List<TreeNode> nodeList = new ArrayList<>();

        for (int nodeIndex = 0; nodeIndex < array.length;nodeIndex++){
            nodeList.add(new TreeNode(array[nodeIndex]));
        }

        //对LastParentIndex-1个父节点按照父节点和子节点的关系建立二叉树
        for (int parentIndex = 0; parentIndex < array.length/2-1;parentIndex++){

            //左孩子
            nodeList.get(parentIndex).left =  nodeList.get(parentIndex * 2 +1);
            //右孩子
            nodeList.get(parentIndex).right =  nodeList.get(parentIndex * 2 +2);

        }

        //最后一个父节点，可能存在没有右孩子的情况，所以拿出来单独处理
        int lastParentIndex = array.length/2-1;

        //左孩子
        nodeList.get(lastParentIndex).left =  nodeList.get(lastParentIndex * 2 + 1);

        //右孩子，如果长度为奇数则建立右孩子
        if(array.length % 2 == 1){
            nodeList.get(lastParentIndex).right = nodeList.get(lastParentIndex * 2 + 2);
        }

        return nodeList;
    }

    //前序遍历,递归方式 先访问根节点，然后前序遍历左子树，再前序遍历右子树。。。此处结果应该为1-2-4-8-9-5-3-6-7
    public static void preOderTraverse(TreeNode node)
    {
        if(node == null)
            return;
        System.out.print(node.key+ " ");
        preOderTraverse(node.left);
        preOderTraverse(node.right);
    }

    //中序遍历,递归方式  先中序遍历根节点的左子树，然后访问根节点最后中序遍历根节点的右子树。此处结果应该为8-4-9-2-5-1-6-3-7
    public static void inOrderTraverse(TreeNode node){

        if(node == null)
            return;
        inOrderTraverse(node.left);
        System.out.print(node.key+" ");
        inOrderTraverse(node.right);

    }

    //后序遍历,递归方式  从左到右后节点的方式访问左右字数，最后访问根节点，左右中的顺序。此处结果应该为,8-9-4-5-2-6-7-3-1
    public static void postOrdeTraverse(TreeNode node){

        if(node == null)
            return;
        postOrdeTraverse(node.left);
        postOrdeTraverse(node.right);
        System.out.print(node.key+" ");

    }

    //层序遍历
    public static void LaywerTraverse(TreeNode node){

        if(node == null)
            return;

        LinkedList<TreeNode> mList = new LinkedList<>();
        mList.add(node);
        TreeNode currentNode;
        while (!mList.isEmpty()){
            currentNode = mList.poll();
            System.out.println(currentNode.key);
            if(currentNode.left != null){
                mList.add(currentNode.left);
            }
            if(currentNode.right != null){
                mList.add(currentNode.right);
            }
        }

    }
}